package main

//#link: https://leetcode-cn.com/problems/max-points-on-a-line/
func main() {

}

func maxPoints(points [][]int) int {
	ans := 0
	n := len(points)
	if n <= 2 {
		return n
	}
	for i, p := range points {
		//至多只能找到 n−i 个点共线或者结果已经大于一半的点了
		if ans >= n-i || ans > n>>1 {
			break
		}
		cnt := map[int]int{}
		for _, q := range points[i+1:] {
			x, y := q[0]-p[0], q[1]-p[1]

			if x == 0 {
				y = 1
			} else if y == 0 {
				x = 1
			} else {
				//控制y为整数保证y+20001*x唯一
				if y < 0 {
					x, y = -x, -y
				}
				g := gcd(abs(x), abs(y))
				x /= g
				y /= g
			}
			cnt[y+20001*x]++
		}
		for _, c := range cnt {
			ans = max(ans, c+1)
		}
	}
	return ans
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
